
//909.蛇梯棋
class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        //根据题意需要找最短路径,考虑使用BFS
        //此题的BFS中的队列存放什么？？？存放左边还是编号？？？
        //用队列存储编号

        //根据编号pos计算横坐标:从下往上行为r=(pos-1)%n,那么从上往下就是n-1-r
        //计算纵坐标,如果r为偶数,纵坐标就是l=(pos-1)%n;如果r是奇数,纵坐标就是n-1-l
        int n=board.size(), step=0;
        vector<int> vist(n*n+1);  //记录那些编号已经去过了
        vist[1]=1;
        queue<int> q;  //记录编号
        q.push(1);
        while(!q.empty())
        {
            int _size=q.size();
            for(int i=0;i<_size;i++)
            {
                int pos=q.front();
                q.pop();
                if(pos==n*n) return step;
                for(int k=1;k<=6&&pos+k<=n*n;k++)
                {
                    int new_pos = pos + k;
                    int _r = (new_pos - 1) / n, r = n - 1 - _r;
                    int _l = (new_pos - 1) % n;
                    if (_r % 2 != 0) _l = n - 1 - _l;   //将编号转化为坐标
                    if(board[r][_l]!=-1) new_pos=board[r][_l];
                    if(vist[new_pos]) continue;   //如果该位置已经来过,就不需要再走了
                    vist[new_pos]=1;
                    q.push(new_pos);
                }
            }
            step++;
        }
        return -1;
    }
};